package main

import (
	"fmt"
)

/**
执行用时：24 ms, 在所有 Go 提交中击败了65.41%的用户
内存消耗：2.8 MB, 在所有 Go 提交中击败了74.91%的用户
 */
func minWindow(s string, t string) string {

	hs, ht := make(map[byte]int, 0), make(map[byte]int, 0)
	for i := 0; i < len(t); i++ { ht[t[i]]++ }

	res := ""
	for i, j, cnt := 0, 0, 0; i < len(s); i++ {
		hs[s[i]]++
		if hs[s[i]] <= ht[s[i]] { cnt++ }
		for j < len(s) && hs[s[j]] > ht[s[j]] {
			hs[s[j]]--
			j++
		}

		if cnt == len(t) {
			if len(res) == 0 || i - j + 1 < len(res) {
				res = s[j:i+1]
			}
		}
	}
	return res
}

func main() {

	fmt.Println(minWindow("ADOBECODEBANC", "ABC"))
}
